package com.cg.leetcode;

import org.junit.Test;

/**
 * 45.跳跃游戏 II
 *
 * @author cg
 * @program LeetCode->LeetCode_45
 * @create 2022-09-01 10:54
 **/
public class LeetCode_45 {

    @Test
    public void test45() {
        System.out.println(jump(new int[]{2, 3, 1, 1, 4}));
    }

    /**
     * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     * 假设你总是可以到达数组的最后一个位置。
     * <p>
     * 示例 1:
     * 输入: nums = [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     * 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     * <p>
     * 示例 2:
     * 输入: nums = [2,3,0,1,4]
     * 输出: 2
     * <p>
     * 提示:
     * 1 <= nums.length <= 10^4
     * 0 <= nums[i] <= 1000
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        // 最大步数result,当前步数覆盖最远距离下标currentDistance,下一步覆盖最远距离下标nextDistance
        int result = 0, currentDistance = 0, nextDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            // 更新下一步覆盖距离
            nextDistance = Math.max(nums[i] + i, nextDistance);
            // 当前下标i到达当前步数覆盖最远距离
            if (currentDistance == i) {
                // 当前最远覆盖距离是终点,直接结束
                if (currentDistance == nums.length - 1) {
                    break;
                } else {
                    // 当前最远覆盖距离不是终点,需要走下一步
                    result++;
                    // 更新当前最远覆盖距离下标
                    currentDistance = nextDistance;
                    // 下一步最远覆盖距离下标到达终点,步数已经加一,直接结束
                    if (nextDistance == nums.length - 1) {
                        break;
                    }
                }
            }
        }
        return result;
    }

}
